package com.ys168.gam.shortestpath.algorithm;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.logging.Level;
import java.util.logging.Logger;

import com.ys168.gam.shortestpath.model.Node;
import com.ys168.gam.shortestpath.uimessage.UIMessageCode;
import com.ys168.gam.shortestpath.uimessage.UIMessageUtil;

/**
 * Dijkstra算法
 *
 * @author Jason Krebs
 * @date 2015年2月5日
 */
public class Dijkstra {

    private static final Logger LOGGER = Logger.getLogger(Dijkstra.class.getName());

    private Set<Node> openNodes;
    private Set<Node> closeNodes;
    private Map<Node, Integer> distance;
    private Map<Node, Node> predecessors;
    private boolean isDirectedGraph;// 是否有向图

    public Dijkstra() {
        this(false);
    }

    /**
     *
     * @param isDirectedGraph
     *            是否有向图
     */
    public Dijkstra(boolean isDirectedGraph) {
        this.isDirectedGraph = isDirectedGraph;
    }

    public void execute(Node source) {
        openNodes = new HashSet<Node>();
        closeNodes = new HashSet<Node>();
        distance = new HashMap<Node, Integer>();
        predecessors = new HashMap<Node, Node>();

        distance.put(source, 0);
        openNodes.add(source);

        while (!openNodes.isEmpty()) {
            Node node = getMinimum(openNodes);// 获取最短路径的节点
            closeNodes.add(node);// 将该节点加入已处理集合中
            openNodes.remove(node);// 将该节点从未处理集合中移除
            findMinimalDistances(node);// 查找最短距离
        }
    }

    private void findMinimalDistances(Node node) {
        List<Node> adjacentNodes = getNeighbors(node);
        for (Node target : adjacentNodes) {
            if (getShortestDistance(target) > getShortestDistance(node) + node.calculateLength(target)) {
                distance.put(target, getShortestDistance(node) + (int) node.calculateLength(target));
                predecessors.put(target, node);
                openNodes.add(target);
            }
        }
    }

    /**
     *
     * @param nodes
     * @return
     */
    private Node getMinimum(Set<Node> openNodes) {
        Node minimum = null;
        for (Node node : openNodes) {
            if (minimum == null) {
                minimum = node;
            } else {
                if (getShortestDistance(node) < getShortestDistance(minimum)) {
                    minimum = node;
                }
            }
        }
        return minimum;
    }

    private List<Node> getNeighbors(Node node) {
        List<Node> neighbors = new ArrayList<Node>();
        List<Node> nodes = isDirectedGraph ? node.getOutNodes() : node.getAllNodes();
        for (Node target : nodes) {
            if (!isSettled(target)) {
                neighbors.add(target);
            }
        }
        return neighbors;
    }

    public List<Node> getPath(Node target) {
        List<Node> path = new LinkedList<Node>();
        Node step = target;

        if (predecessors.get(step) == null) { // check if a path exists
            return path;
        }
        path.add(step);
        while (predecessors.get(step) != null) {
            step = predecessors.get(step);
            path.add(step);
        }

        Collections.reverse(path); // Put it into the correct order
        return path;
    }

    /**
     * 获取最短距离
     *
     * @param destination
     * @return
     */
    private int getShortestDistance(Node destination) {
        Integer d = distance.get(destination);
        return d == null ? Integer.MAX_VALUE : d;
    }

    private boolean isSettled(Node node) {
        return closeNodes.contains(node);
    }

    public void printPath(Node target) {
        List<Node> path = getPath(target);
        if (path == null) {
            LOGGER.log(Level.WARNING, UIMessageUtil.getString(UIMessageCode.LOG_04), target.getIndex());
            return;
        }
        for (Node node : path) {
            LOGGER.log(Level.INFO, node.getIndex() + "");
        }
    }

}
